#define _CRT_SECURE_NO_WARNINGS 1

#include <iostream>
#include <queue>
#include <stack>

using namespace std;

void Method1()
{
	int count = 18;
	int a = 1;
	int b = 1;
	int c = b + a;
	cout << a << " " << b << " ";
	while (count--)
	{
		cout << c << " ";
		a = b;
		b = c;
		c = a + b;
	}
}

int Method2(int n)
{
	if (n < 3) return 1;
	return Method2(n - 1) + Method2(n - 2);
}

void Method3(int n)
{
	queue<int> q({ 1, 1 });

	while (n--)
	{
		int tmp = q.front();
		q.pop();
		cout << tmp << " ";
		q.push(q.front() + tmp);
	}
}

void Method4(int n)
{
	stack<int> s({ 1, 1 });
	cout << "1" << " " << "1" << " ";

	n -= 2;
	while (n--)
	{
		int tmp = s.top();
		s.pop();
		int c = tmp + s.top();
		cout << c << " ";
		s.push(tmp);
		s.push(c);
	}
}

void Method5(int n)
{
	int arr[20];
	arr[0] = arr[1] = 1;

	for (int i = 2; i < n; i++)
	{
		arr[i] = arr[i - 1] + arr[i - 2];
	}
	for (auto a : arr)
	{
		cout << a << " ";
	}
}
int main()
{
	int count = 20;
	Method1();
	cout << endl;
	for (int i = 1; i <= count; i++)
	{
		cout << Method2(i) << " ";
	}
	cout << endl;
	Method3(count);

	cout << endl;
	Method4(count);
	
	cout << endl;
	Method5(count);
	return 0;
}
